//***********************************直接插入排序***************************************
// 顺序查找插入位置： 直接插入排序
//初始时，默认第一个数据是已经排序的，后面的数据是未排序的
//从第二个开始，寻找目标值在其前面的子序列中的插入位置，并插入
//最好时间复杂度O(n)，最坏O(n²)，空间复杂度O(1)
function insertSort_normal(arr) {
  //从数组的第二个元素开始遍历
  for (let i = 1; i <= arr.length - 1; i++) {
    //保存目标元素
    let temp = arr[i]
    //目标元素与目标元素之前的有序序列逐个比较，若小了则停止遍历并插入
    let j = i - 1;
    for (; j >= 0 && temp < arr[j]; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = temp;
  }
}


function insertSort(arr) {
  for (let i = 1; i <= arr.length - 1; i++) {
    let temp = arr[i];
    let j = i - 1;
    for (; j >= 0; j--) {
      if (arr[j] >= temp) {
        arr[j + 1] = arr[j]
      } else {
        break;
      }
    }
    arr[j + 1] = temp;
  }
}
//测试用例
let arr = [96, 29, 54, 23, 83, 16, 32, 7, 10, 3, 5, 23]
insertSort_normal(arr);
console.log(arr);


